|
The balls-into-bins problem is a classic problem in probability theory that has many applications in computer science. The problem involves ''m'' balls and ''n'' boxes (or "bins"). Each time, a single ball is placed into one of the bins. After all balls are in the bins, we look at the number of balls in each bin; we call this number the ''load'' on the bin and ask: what is the maximum load on a single bin? Obviously, it is possible to make the load as small as ''m''/''n'' by putting each ball into the least loaded bin. The interesting case is when the bin is selected at random, or at least partially at random. == Random allocation== When the bin for each ball is selected at random, independent of other choices, the maximum load might be as large as ''m''. However, it is possible to calculate a tighter bound that holds with high probability. A "high probability" is a probability 1-o(1), i.e. the probability tends to 1 when ''n'' grows. For the case ''m''=''n'', with high probability the maximum load is: The maximum load can also be calculated for ''m''<>''n''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Balls into bins」の詳細全文を読む スポンサード リンク
|